The present invention relates to a technology for searching a network address in a so-called pipeline system.
As Internet users and construction of local area networks (LANs) in enterprises increase in recent years, ternary content addressable memories (TCAMs) serving as address search apparatuses are used frequently in routers at relay points on a network in order to enhance the processing capability. Hereafter, the TCAM will be explained by referring to FIGS. 15 to 20. FIG. 15 is a diagram which shows a configuration example of a network system in which the TCAM serving as the address search apparatus is used. FIG. 16 is a diagram which shows a classifying algorithm of packets using hardware processing. FIG. 17 is a concept diagram which shows a basic configuration and search operation of the TCAM. FIG. 18 is a block diagram which shows a detailed configuration of the TCAM. FIG. 19 is a concept diagram which shows a configuration of a conventional TCAM cell shown in FIG. 18.
FIG. 15 shows a system example shown in xe2x80x9cAlgorithms for Packet Classificationxe2x80x9d IEEE Network, March/April 2001. In FIG. 15, a network 1601 is administered by an Internet service provider (ISP1). An intra-enterprise network (E1) 1603 is connected to the network 1601 via a router at a relay point (xe2x80x9cjunction routerxe2x80x9d) 1602. An intra-enterprise network (E2) 1605 is connected to the network 1601 via a junction router 1604.
In addition, a network access point (NAP) 1607 is connected to the network 1601 via a junction router 1606. A network 1608 administered by an Internet service provider (ISP2) and a network 1609 administered by an Internet service provider (ISP3) are connected to the NAP 1607.
In the junction routers 1602, 1604 and 1606 in the configuration heretofore explained, a rule stated in a header of a received packet is looked up, and packet classification is conducted. For example, in the junction router 1606, packets received from the NAP 1607 are classified, such as xe2x80x9cthis packet should go to the intra-enterprise network E1xe2x80x9d, xe2x80x9cthis packet should not go to the intra-enterprise network E1, but hop to the intra-enterprise network E2xe2x80x9d, and xe2x80x9cthis packet should not go anywherexe2x80x9d.
In headers of packets, such various kinds of information are stated in the form of rules, and they serve as search keys for classification in junction routers. In each junction router, it is necessary to look up what action each of all rules included in various received packets requires and to instantaneously determine to which routers the respective packets should be delivered (hopped).
There are various techniques for the packet classification (xe2x80x9cAlgorithms for Packet Classificationxe2x80x9d IEEE Network, March/April 2001). Today, a packet classification algorithm using hardware processing as shown in FIG. 16 is used most frequently. In this algorithm, special hardware called ternary content addressable memory (TCAM) is used.
With reference to FIG. 16, in the packet classification algorithm using hardware processing, a TCAM 1701, a priority encoder 1702, and an action memory 1703 are used.
In the TCAM 1701, a rule is held every entry. Since TCAM in these days is too expensive, only a rule name, i.e., only a label is typically held in each entry. An action to be subsequently executed is stored in the action memory 1703 formed of comparatively inexpensive DRAMs or SRAMs.
If a rule as a destination address is given to an input pin of the TCAM 1701 from the packet, parallel coincidence comparison is started all at once between the rule given to the input pin and internally held rules. And an entry number (or entry numbers) bearing coincidence or a highest resemblance is output. For example, if a rule (R4, R5 and R6) is given, an entry number #3 is output.
When there are plurality of search results of the TCAM 1701, the priority encoder 1702 supplies an entry having a lowest number to the action memory 1703 as an entry having high priority. With respect to the entry input from the priority encoder 1702, the action memory 1703 searches out an action to be subsequently conducted. As a result, the next router is specified and a packet is transferred. Hopping to the next step is thus conducted.
For example, if a rule is an IP address, an xe2x80x9cXxe2x80x9d value (don""t care) is often used. This means that it is removed from search targets of coincidence comparison. If a stored value is xe2x80x9cXxe2x80x9d, the TCAM 1701 determines it to be unconditional coincidence. Therefore, information to be stored by an internal cell of the TCAM 1701 also becomes ternary, xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d and xe2x80x9cXxe2x80x9d. The name of ternary CAM (content addressable memory) comes from this.
A basic hardware configuration of the TCAM and basic operation of the search will now be explained by referring to FIG. 17. In FIG. 17, a search port 1801 is provided in the TCAM. In the search port 1801, a data sequence of a search command is disposed. A plurality of TCAM cells 1802 are provided in each of entries (entries #0 to #n). The plurality of TCAM cells 1802 are connected to the data sequence of the search port 1801 by search operation bit lines (search lines) 1803 in one-to-one correspondence. The plurality of TCAM cells 1802 provided for each of entries (entries #0 to #n) are connected in common to a search output line (match line) 1804. Each of the TCAM cells 1802 stores a ternary value of xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d, or xe2x80x9cXxe2x80x9d.
If the search command is supplied to an input pin, not shown, at the time of search operation, then the search command is transferred to the search port 1801, and the data sequence of the search command is disposed on the search operation bit lines 1803 and transferred to all TCAM cells 1802 of each entry. As a result, comparison is simultaneously started in all entries to determine whether the data sequence coincides with data held in the TCAM cells 1802.
The search output line 1804 is precharged to a high (xe2x80x9cHxe2x80x9d) level before the search operation is started. Typically, on a search output line 1804 connected to coincident TCAM cells 1802, the xe2x80x9cHxe2x80x9d level is held as it is. On the other hand, on a search output line 1804 connected to a non-coincident TCAM cell 1802, discharge is conducted via a transistor in the cell and the search output line 1804 is lowered to a low (xe2x80x9cLxe2x80x9d) level. In other words, the TCAM 1701 serving as an address search apparatus shown in FIG. 16 checks the entry number of the search output line 1804 that holds the xe2x80x9cHxe2x80x9d level and outputs the entry number to the priority encoder 1702. This is the role of the TCAM 1701.
A detailed configuration of the TCAM and outline of its search operation will be explained with reference to FIG. 18. As shown in FIG. 18, the TCAM includes a data input/output pin 1901, a command control pin 1902, an address input pin 1903, and a search result output pin 1904 as pins for connection to the outside.
A command decoder 1921 is connected to the command control pin 1902. A command supplied to the command control pin 1902 is decoded by the command decoder 1921. An operation command resulting from the decoding is sent to each section.
A decoder 1931 is connected to the address input pin 1903. A row decoder 1932 is connected to an output terminal of the decoder 1931. An output terminal of a search encoder 1941 is connected to the search result output pin 1904.
Between an output terminal of each row of the row decoder 1932 and an input terminal of a corresponding row of the search encoder 1941, a plurality of TCAM cells 1910 are arranged so as to form one lateral line. A mask data word line 1933 and a valid data word line 1943 are connected to the output terminal of each row of the row decoder 1932. A plurality of TCAM cells arranged in one lateral line are connected to the mask data word line 1933 and the valid data word line 1943 in parallel.
A search output line (match line) 1942 is connected to the input terminal of each row of the search encoder 1941. A plurality of TCAM cells 1910 arranged in one lateral line are connected to each search output line 1942 in parallel.
A plurality of sense amplifiers 1911 and a plurality of search drivers 1912 and 1913 are connected to the data input/output pin 1901. The plurality of sense amplifiers 1911 and the plurality of search drivers 1912 and 1913 are connected on one terminal side of each column of a plurality of TCAM cells 1910 arranged in one lateral line in one-to-one correspondence.
Bit lines 1914 and 1915 for a write operation, a read operation and a refresh operation are provided for each of the sense amplifiers 1911. A plurality of TCAM cells 1910 in each column of the plurality of TCAM cells 1910 arranged in one lateral line are connected to the two bit lines 1914 and 1915 in parallel.
Search operation bit lines (search lines) 1916 and 1917 are connected to a plurality of search drivers 1912 and 1913, respectively. The plurality of TCAM cells 1910 in each column of the plurality of TCAM cells 1910 arranged in one lateral line are connected to the two search operation bit lines 1916 and 1917 in parallel.
When writing data in the TCAM cells 1910 in the configuration heretofore explained, a write command is supplied to the command control pin 1902. Data to be written is supplied to the data input/output pin 1901. An address and an entry number in which the data should be written are supplied to the address input pin 1903.
With respect to the write command, the address input is not needed so much. What is finally needed is the next action corresponding to each rule (input data). Therefore, rather than whether data is input to the TCAM entry, it is necessary to administer only the entry of the TCAM and lookup of the next action memory. Therefore, data may be input to empty entries in order. In order to look up the entry in which the data has been written, address information can be output to the search result output pin 1904 at the time of data writing.
Write data is transferred to the two bit lines 1914 and 1915 by a write buffer circuit incorporated in the sense amplifier 1911. At the same time, the write address is input to the row decoder 1932 via the decoder 1931, and the data is written into TCAM cells 1910 in the desired entry.
A search operation will also be explained below. A search command is supplied to the command control pin 1902, and a data sequence to be searched is also supplied to the data input/output pin 1901. At the time of search, the data sequence is transferred to the search operation bit lines 1916 and 1917 via the search drivers 1912 and 1913. At this time, the search output line 1942 is previously precharged to the xe2x80x9cHxe2x80x9d level before the search operation is started.
In the TCAM cells 1910, comparison is made whether the held data and the search operation bit lines 1916 and 1917 are coincident. A search output line 1942 connected to only an entry in which the whole data sequence has coincided holds the xe2x80x9cHxe2x80x9d level. If there is non-coincidence even in one bit, the entry connected to the search output line 1942 lowers the level of the search output line 1942 to the xe2x80x9cLxe2x80x9d level by discharge through a transistor in the cell. This is conducted by wired-OR processing.
In the search encoder 1941, a search output line 1942 on which the whole data sequence coincides and holds the xe2x80x9cHxe2x80x9d level is found out. The number of the entry to which the search output line 1942 that holds the xe2x80x9cHxe2x80x9d level belongs is output from the search result output pin 1904.
Each of the conventional TCAM cells 1910 shown in FIG. 18 has, for example, a configuration as shown in FIG. 19. In FIG. 19, the conventional TCAM cell 1910 is formed so as to hold a ternary value of xe2x80x9c1xe2x80x9d, xe2x80x9c0xe2x80x9d or xe2x80x9cXxe2x80x9d by a combination of two physical cells, a valid data storage cell 2001 and a mask data storage cell 2002.
Each of the valid data storage cell 2001 and the mask data storage cell 2002 has two inverters connected in an anti-parallel form so as to form a flip-flop.
A first storage terminal of the valid data storage cell 2001 is connected to a MOS transistor 2011 at its source electrode, and connected to a MOS transistor 2012 at its gate electrode. A second storage terminal is connected to a MOS transistor 2013 at its source electrode, and connected to a MOS transistor 2014 at its gate electrode. The MOS transistor 2011 is connected at its drain electrode to a bit line 2015. The MOS transistor 2013 is connected at its drain electrode to a bit line 2016. Gate electrodes of the MOS transistors 2011 and 2013 are connected in common to a valid data word line 2017. The MOS transistors 2012 and 2014 are connected in series. One terminal of the series connection is connected to a search operation bit line 2018, and the other terminal is connected to a search operation bit line 2019.
A first storage terminal of the mask data storage cell 2002 is connected to a MOS transistor 2021 at its source electrode. A second storage terminal is connected to a MOS transistor 2022 at its source electrode, and connected to a MOS transistor 2023 at its gate electrode. The MOS transistor 2021 is connected at its drain electrode to a bit line 2024. The MOS transistor 2022 is connected at its drain electrode to a bit line 2025. Gate electrodes of the MOS transistors 2021 and 2022 are connected in common to a mask data word line 2026. The MOS transistors 2023 is connected at its source electrode to ground, and connected at its drain electrode to a MOS transistor 2027 at its source electrode. The MOS transistor 2027 is connected at its gate electrode to a connection terminal between the MOS transistors 2012 and 2014 connected in series. The MOS transistor 2027 is connected at its drain electrode to a search output line 2030.
In the TCAM cell used in the conventional network address search apparatus (LSI), two physical cells, i.e., a SRAM (static random access memory) cell and a search (coincidence comparison) cell are thus formed by using, for example, 16 MOS transistors as shown in FIG. 19 in order to represent a ternary value of xe2x80x9c1xe2x80x9d, xe2x80x9c0xe2x80x9d, and xe2x80x9cXxe2x80x9d.
A search operation in the TCAM cell is represented by the following expression.
If ([val=1xe2x80x2b0]andand[mas=1xe2x80x2b1]) then WORD less than =1xe2x80x2b0
If ([val=1xe2x80x2b1]andand[mas=1xe2x80x2b1]) then WORD less than =1xe2x80x2b1
If ([val=1xe2x80x2bx]andand[mas=1xe2x80x2b0]) then WORD less than =1xe2x80x2bx
In other words, if a mask bit held in the mask data storage cell 2002 is xe2x80x9c1xe2x80x9d, then it is determined whether a valid bit held in the valid data storage cell 2001 coincides with the search operation bit lines 2018 and 2019, and a search result is output to the search output line 2030. When the mask bit held in the mask data storage cell 2002 is xe2x80x9c0xe2x80x9d, then the MOS transistors 2023 and 2027 do not turn on and consequently the search output line 2030 is never connected to the ground level (GND).
However, the conventional TCAM cell has the following problems. First, in the conventional TCAM cell, two physical cells, i.e., the SRAM cell and the search (coincidence comparison) cell are formed by using, for example, 16 MOS transistors as shown in FIG. 19. This results in a problem that the area occupied by each cell is large and consequently TCAM cells of a large capacity cannot be mounted on LSI silicon. It is the actual state that only a capacity of 9 Mbits at most can be ensured. This is evident by comparison with today""s SRAM formed of six MOS transistors and today""s dynamic random access memory (DRAM) formed of one MOS transistor and one capacitor.
FIG. 20 shows the search operation to facilitate understanding. A TCAM cell array 2101 shown in FIG. 20 is formed of the whole number of rows each in which a plurality TCAM cells 1910 are arranged in one lateral line as shown in FIG. 18. A search driver 2102 is a collective representation of the search drivers 1912 and 1913 shown in FIG. 18. In the search driver 2102, there is provided a search line SL serving as a search operation bit line in each column including a plurality of TCAM cells. A match line ML serving as a search output line is provided in each row including a plurality of TCAM cells arranged in one lateral line.
With reference to FIG. 20, in the conventional search operation, search data is supplied to all TCAM cells in parallel all at once by the search lines SL. As a result, all TCAM cells drive all match lines ML. In general, the basic operation, such as read operation or write operation of a memory is conducted on a limited portion of the whole memory. Unlike this, the search operation is conducted for all TCAM cells in the vertical direction and the horizontal direction. Therefore, power consumption becomes extremely large. For example, the power consumption amounts to 6 W when the capacity is 4 Mbits, and the power consumption amounts to 10 W when the capacity is 9 Mbits. This also makes mounting of the TCAM cells of a large capacity more difficult. In addition, the large power consumption causes a problem that it is difficult to implement a system LSI as a network address search apparatus increased in search operation speed.
In addition, the conventional TCAM typically includes the TCAM 1701 and the priority encoder 1702. Within the TCAM, data having higher priority can be rewritten so as to have a lower entry number. Therefore, if hit in the search operation of the conventional TCAM occurs in a plurality of entries, data having higher priority, i.e., data having a lower entry number is output. For example, an IP address that has come into a state that nobody accesses it is erased on demand (which is called ageing), and rearrangement is conducted again in the order of descending priority.
In fact, this re-addressing is a work of very large overhead. This is because data rewriting must be executed for all entries. During this interval, search operation cannot be accepted. In order to solve these problems, for example, a configuration as shown in FIG. 21 is conceivable. FIG. 21 is a block diagram which shows a configuration example that solves the problems caused when the re-addressing is executed by using the conventional TCAM.
With reference to FIG. 21, each of TCAM 2201 and TCAM 2202 includes the TCAM 1701 and the priority encoder 1702 shown in FIG. 16 as explained above. The TCAM 2201 is connected to a write line 2204 and a search line 2205 via an address decoder 2203. In the same way, the TCAM 2202 is connected to the write line 2204 and the search line 2205 via an address decoder 2206.
According to this configuration, the same data is written into the TCAM 2201 and TCAM 2202. If rewriting of priority occurs, rewriting is executed, for example, for only the TCAM 2201. During that interval, search can be allowed for the TCAM 2202 and a search result is output. As a matter of course, search is executed for only old data preceding rewriting. Subsequently, when rewriting has been completed for the TCAM 2201, the search port is switched from the TCAM 2202 to the TCAM 2201 and the search is executed. When rewriting is necessary, rewriting can be executed for the TCAM 2202. The search command can be executed continuously irrespective of the rewriting command.
In the configuration shown in FIG. 21, however, a plurality of TCAMs are needed although the TCAM itself is very expensive hardware, resulting in a further higher cost. Furthermore, the search speed cannot catch up with requirements of the network system in recent years. Since the power consumption is high, however, improvement of the search speed is very difficult.
That is, the search speed that can be attained with today""s TCAM hardware is approximately 100 Mpps (100 mega-packets per second) at most. For example, in 40GLAN, however, the commercial demand is (40 Gbits/20 bytes) 250 MHz, i.e., 250 Mpps (250 mega-packets per second). Performance that is 25 times as high as the current performance is needed.
In addition, the conventional TCAM typically has an LSI structure including the TCAM 1701 and the priority encoder 1702 shown in FIG. 16. Thus, the conventional TCAM is not a system LSI including the action memory 1703 as well. In the conventional art, therefore, a TCAM LSI including the TCAM 1701 and the priority encoder 1702, and an action memory LSI having only the action memory 1703 are disposed on a system board. A search result obtained in the TCAM LSI is encoded. The encoded result is input to the action memory LSI. From the viewpoint of application, this configuration is inconvenient to use.
It is an object of this invention to provide a TCAM cell reduced in area occupied by the cell so as to make it possible to mount TCAM cells of a large capacity on an LSI, a CAM cell array and a TCAM cell array capable of executing the search operation with low power consumption and consequently capable of operating at high speed, an address search memory using such a TCAM cell array, and a network address search apparatus implemented as a system LSI that can be conveniently used.
The content addressable memory cell array according to one aspect of this invention includes a first memory cell array and a second memory cell array. Each of the first and second memory cell arrays includes a plurality of content addressable memory cells arranged in rows and columns, a plurality of search line pairs respectively connected to ones of the content addressable memory cells arranged in the columns, a plurality of match lines respectively connected to ones of the content addressable memory cells arranged in the rows, and a plurality of precharge circuits respectively connected to the match lines, each precharging the match line connected thereto. Each of the content addressable memory cells includes a coincidence comparison circuit comparing data stored in each of the content addressable memory cell with data on the search line pairs connected to each of the content addressable memory cells and providing a comparison result of coincidence or non-coincidence for the match line connected to each of the content addressable memory cells after being precharged. The content addressable memory cell array further includes a plurality of storage circuits storing results of the comparison on the match lines of the first memory cell array, respectively. The content addressable memory cell array also includes a plurality of control circuits provided correspondingly to the storage circuits and controlling the precharge circuits of the second memory cell array, each preventing the precharge circuit to be controlled from precharging the match line connected to the precharge circuit to be controlled when the corresponding storage circuit stores the comparison result of the non-coincidence.
The content addressable memory cell array according to another aspect of this invention includes a first memory cell array and a second memory cell array. Each of the first and second memory cell arrays includes a plurality of content addressable memory cells arranged in rows and columns, a plurality of search line pairs respectively connected to ones of the content addressable memory cells arranged in the columns, and a plurality of match lines respectively connected to ones of the content addressable memory cells arranged in the row. Each of the content addressable memory cells includes a coincidence comparison circuit comparing data stored in each of the content addressable memory cells with data on the search line pairs connected to each of the content addressable memory cells and providing a comparison result of coincidence and non-coincidence for the match line connected to each of the content addressable memory cells. The second memory cell array further includes a plurality of drivers driving search line pairs of the second memory cell array, respectively, and a search control circuit connected to the match lines of the first memory cell array and controlling to prevent the driver from driving the search line pairs of the second memory cell array.
Other objects and features of this invention will become apparent from the following description with reference to the accompanying drawings.